package com.zdb.algorithm.dac;

public class Hanoitower {

    private static long cnt = 0L;

    public static void main(String[] args) {

        hanoitower(10, 'A', 'B', 'C');
        System.out.println("总共搬运次数：" + cnt);
    }

    /**
     * 将第num个盘子从a移动到c，中间可以利用b
     * @param num
     * @param a
     * @param b
     * @param c
     */
    public static void hanoitower(int num, char a, char b, char c) {
        // 只有一个盘子时，直接从a 移动到 c
        if(num == 1) {
            cnt++;
            System.out.println("移动【" + num + "】从[" + a + "]到[" + c + "]");
        } else {
            // 如果有两个及以上的盘子，
            // 将num个盘子分成两个部分：1. 最底下那个盘子；2.除最底下那个盘子之外的所有盘子
            // 将 num-1个盘子，从 a 移动 到 b,借助c
            hanoitower(num-1, a, c, b);

            // 将 第num个盘子，从a 移动到c,不需要借助其他柱子
            cnt++;
            System.out.println("移动【" + num + "】从[" + a + "]到[" + c + "]");

            // 将 num-1个盘子从 b 移动到c, 借助a
            hanoitower(num-1, b, a, c);

        }

    }
}
